/* date 04-01-2012 by Marcel Hekman
 */

package mazeAssignment.solve;

import mazeAssignment.*;

public class DeadendChaseSolve implements Solve
{
	private Maze maze;
	private boolean isFinished;
	private int posX, posY;
	private int chaseX, chaseY;
	
	@Override
	public void initialise(Maze m) throws SolveException
	{
		this.maze = m;
		this.isFinished = false;
		this.posX = 0;
		this.posY = 0;
		this.chaseX = -1;
		this.chaseY = -1;
	}

	@Override
	public boolean isDone()
	{
		return isFinished;
	}

	@Override
	public void tick() throws SolveException
	{
		if(isFinished)
			throw new SolveException("DeadendFillSolve.tick(): Already finished!");
		
		if(chaseX != -1 && chaseY != -1) {
			if(chaseTick()) {
				return;
			}
		}
		
		if(fillOneGap()) {
			return;
		}
		
		//We're at the end of the maze start from the beginning.
		//Reset the current row number.
		posX = 0;
		posY = 0;
		
		//A full run changed nothing, so we're finished.
		if(!fillOneGap())
		{
			isFinished = true;
			return;
		}
	}
	
	private boolean chaseTick() throws SolveException
	{
		//North
		if(chaseY - 1 >= 0 && tryElement(chaseX, chaseY - 1)) {
			chaseY = chaseY - 1;
		}
		//West
		else if(chaseX - 1 >= 0 && tryElement(chaseX - 1, chaseY)) {
			chaseX = chaseX - 1;
		}
		//South
		else if(chaseY + 1 < maze.getSizeY() && tryElement(chaseX, chaseY + 1)) {
			chaseY = chaseY + 1;
		}
		//East
		else if(chaseX + 1 < maze.getSizeX() && tryElement(chaseX + 1, chaseY)) {
			chaseX = chaseX + 1;
		}
		else {
			chaseX = -1;
			chaseY = -1;
			return false;
		}
		return true;
	}
	
	/**
	 * Searches the entire maze for a dead-end element.
	 * Saves and resumes from a previously saved row.
	 * And start from the beginning if we reach the end. (only start from the beginning once)
	 * @return True if a gap was filled.
	 * If not the algorithm is finished because it cannot fill anymore gaps.
	 */
	private boolean fillOneGap()
	{
		int xSize = maze.getSizeX();
		int ySize = maze.getSizeY();
		
		//Continue from the last position
		for(int y = posY; y < ySize; y++)
		{
			for(int x = posX; x < xSize; x++)
			{
				if(tryElement(x, y))
				{
					//Save the current row number.
					posX = x;
					posY = y;
					chaseX = x;
					chaseY = y;
					return true;
				}
			}
			//Reset the x position so it won't make a curve shape during solve.
			posX = 0;
		}
		
		return false;
	}
	
	/**
	 * Checks if a node is a is a dead end.
	 * @param x Coordinate.
	 * @param y Coordinate.
	 * @return True if the element is a dead-end and marked. Else false.
	 */
	private boolean tryElement(int x, int y)
	{
		//SOLVE_START and SOLVE_END are obviously not a dead end.
		//Skip SOLVE_INVALID too because it is already marked.
		if(maze.getSolveState(x, y) == Maze.SOLVE_START
		|| maze.getSolveState(x, y) == Maze.SOLVE_END
		|| maze.getSolveState(x, y) == Maze.SOLVE_INVALID)
		{
			return false;
		}
		
		int xSize = maze.getSizeX();
		int ySize = maze.getSizeY();
		
		//Count all accessible directions.
		int blockedDirections = 0;
		
		//North
		if(y == 0 || maze.getNorth(x, y)
		|| maze.getSolveState(x, y-1) == Maze.SOLVE_INVALID)
		{
			blockedDirections++;
		}
		
		//East
		if(x+1 == xSize || maze.getEast(x, y)
		|| maze.getSolveState(x+1, y) == Maze.SOLVE_INVALID)
		{
			blockedDirections++;
		}
		
		//South
		if(y+1 == ySize || maze.getSouth(x, y)
		|| maze.getSolveState(x, y+1) == Maze.SOLVE_INVALID)
		{
			blockedDirections++;
		}
		
		//West
		if(x-1 == xSize || maze.getWest(x, y)
		|| maze.getSolveState(x-1, y) == Maze.SOLVE_INVALID)
		{
			blockedDirections++;
		}
		
		//A dead end
		if(blockedDirections > 2)
		{
			maze.markAsInvalid(x, y);
			return true;
		}
		return false;
	}
}
